package com.algorithm.recursive;

/**
 * 矩形覆盖
 * 题目：我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，从同一个方向看总共有多少种不同的方法？
 * 思路：仔细审题，需要生成宽度为2的一个矩形。所以在宽度角度看有两种方式要不就是竖着一块，要不就是横着两块
 * 那我们生成公式就是 f（n）=f(n-1)+f(n-2);  公式很熟悉为斐波那契数列公式
 * 那我们来确认一下前面的几个值 f(0)=0;f（1）=1;f(2)=2;
 */
public class RectCover {

    public static void main(String[] args) {
        System.out.println(rectCover(4));
    }

    public static int rectCover(int target) {
            if (target<=2){
                return target;
            }else {
                return rectCover(target-1)+rectCover(target-2);
            }
    }
}
